package dynamic;

public class KnapsackProblem {
    private int[] values;
    private int[] weights;

    public KnapsackProblem(int[] values, int[] weights) {
        this.values = values;
        this.weights = weights;
    }

    public int maxValue(int goalWeight) {
        if (goalWeight == 0 || values.length != weights.length || values.length == 0)
            return 0;
        int[][] maxValue = new int[values.length][goalWeight+1];

        for(int i =1;i<maxValue.length;i++){
            //j表示重量
            for(int j = 1;j<maxValue[i].length;j++){
                if(j<weights[i]){
                    maxValue[i][j] = maxValue[i-1][j];
                }
                else
                maxValue[i][j] = Math.max(maxValue[i-1][j],values[i] + maxValue[i-1][j-weights[i]]);
            }
        }

        return maxValue[values.length-1][goalWeight];
    }
    public int max(int num1,int num2){
        if(num1>num2)
            return num1;
        return num2;
    }
}
